package pro.softzhang.algo.lc100;

import com.alibaba.fastjson.JSON;
import pro.softzhang.algo.flag.knowledge.KDoublePointer;
import pro.softzhang.algo.flag.theme.TMathArith;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 167. 两数之和II
 * https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/
 * 输入：numbers = [1,2,4,6,10], target = 8
 * 输出：[1,3]
 * 解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
 */
@TMathArith
public class LC167_TwoSumIIInputArrayIsSorted {
    public static void main(String[] args) {
        int[] numbers = new int[]{1,2,4,6,10};
        int target = 8;
        System.out.println(JSON.toJSONString(new Solution().twoSum(numbers, target)));
    }

    /**
     *
     */
    @KDoublePointer
    static
    class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int h = 0, t = numbers.length - 1;
            while (h < t && numbers[h] + numbers[t] != target) {
                if(numbers[h] + numbers[t] > target) {
                    t--;
                } else {
                    h++;
                }
            }
            return new int[]{h + 1, t + 1};
        }
    }

    @KDoublePointer
    @XOptimal
    static
    class Solution1 {
        public int[] twoSum(int[] numbers, int target) {
            int l = 0, r = numbers.length - 1;
            while (numbers[l] + numbers[r] != target) {
                if (numbers[l] + numbers[r] > target) {
                    r--;
                } else {
                    l++;
                }
            }
            return new int[]{l + 1, r + 1};
        }
    }
}
